// 我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

// 比如n=3时，2*3的矩形块有3种覆盖方法：
function rectCover(n)
{
    // write code here
   let dp=[]
    dp[0]=0
    dp[1]=1
    dp[2]=2
    for(let i=3;i<=n;i++){
        dp[i]=dp[i-1]+2*dp[i-2]
    }
    return dp[n]
}//dp版
function rectCover(n) {
    if(n==1)return 1
    if(n==2)return 2
    return rectCover(n-1)+rectCover(n-2)
}//递归版